package cn.zifangsky.tree.generictree.questions;

import cn.zifangsky.tree.generictree.TreeNode;
import org.junit.Test;

/**
 * 遍历目录树结构
 *
 * @author zifangsky
 * @date 2018/11/11
 * @since 1.0.0
 */
public class Question1 {

    /**
     * 遍历目录树结构
     * @author zifangsky
     * @date 2018/11/11 17:45
     * @since 1.0.0
     * @param paths 路径数组
     */
    private void printDirStructure(String[] paths){
        if(paths != null && paths.length> 0){
            TreeNode<String> root = null;

            //1. 遍历路径数组构造通用树
            for(String path : paths){
                //按照/分割字符串，形成一条目录路径
                String[] dirs = path.split("/");
                //TODO 为了代码健壮性，这里还应该校验目录路径的每一层目录都不能为空字符串
                if(root == null){
                    root = new TreeNode<>(dirs[0]);
                }

                TreeNode<String> currentNode = root;
                //查找当前目录路径与已知的树之间的最底层的公共节点（找到这个节点后置为true）
                boolean lastCommonNodeFlag = false;
                //将一条目录路径上面的各个节点插入到树中的相应位置
                loop: for(String dir : dirs){
                    if(!lastCommonNodeFlag){
                        //如果前面路径的节点相同，则一直寻找currentNode的子节点
                        if(currentNode.getData().equals(dir)){
                            if(currentNode.getFirstChild() != null){
                                //将当前节点设置为其孩子节点，然后继续判断
                                currentNode = currentNode.getFirstChild();
                            }else{
                                lastCommonNodeFlag = true;
                            }
                            continue;
                        }

                        //如果当前节点的数据不等于待插入的路径节点，则应该继续在当前节点的兄弟节点中查找
                        while (currentNode.getNextSibling() != null){
                            currentNode = currentNode.getNextSibling();
                            //如果前面路径的节点相同，则一直寻找currentNode的子节点
                            if(currentNode.getData().equals(dir)){
                                if(currentNode.getFirstChild() != null){
                                    currentNode = currentNode.getFirstChild();
                                }else{
                                    lastCommonNodeFlag = true;
                                }
                                continue loop;
                            }
                        }

                        //兄弟节点中也没找到，则将待插入的路径节点设置为最右边兄弟节点的兄弟节点
                        lastCommonNodeFlag = true;
                        TreeNode<String> temp = new TreeNode<>(dir);
                        currentNode.setNextSibling(temp);
                        currentNode = temp;
                    }
                    //剩余的都是需要在原来的树上新增的节点
                    else{
                        TreeNode<String> temp = new TreeNode<>(dir);
                        currentNode.setFirstChild(temp);
                        currentNode = temp;
                    }
                }

            }

            //2. 遍历通用树，输出需要的目录层次信息
            this.printDirs(root, 0);
        }
    }

    /**
     * 通用树的遍历方法（类似于二叉树的前序遍历）
     * @author zifangsky
     * @date 2018/11/11 18:01
     * @since 1.0.0
     * @param root 当前根节点
     * @param level 表示当前节点的层级
     */
    private void printDirs(TreeNode<String> root, int level){
        if(root != null){
            //1. 输出数据
            for(int i=0;i<level*4;i++){
                System.out.print(".");
            }
            System.out.print(root.getData() + "\n");

            //2. 递归调用此方法遍历子节点
            printDirs(root.getFirstChild(), (level + 1));

            //3. 递归调用此方法遍历兄弟节点
            printDirs(root.getNextSibling(), (level));
        }
    }

    /**
     * 测试用例
     */
    @Test
    public void testMethods(){
        String[] paths = {"a/b/c1", "a/d/c2/e", "e/f/g", "j/k", "e/f/h/i", "m/n"};
//        String[] paths = {"a/b/c", "a/e/f", "a/b/d"};

        this.printDirStructure(paths);
    }

}
